//<p>你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，<strong>如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警</strong>。</p>
//
//<p>给定一个代表每个房屋存放金额的非负整数数组，计算你<strong> 不触动警报装置的情况下 </strong>，一夜之内能够偷窃到的最高金额。</p>
//
//<p> </p>
//
//<p><strong>示例 1：</strong></p>
//
//<pre>
//<strong>输入：</strong>[1,2,3,1]
//<strong>输出：</strong>4
//<strong>解释：</strong>偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
//     偷窃到的最高金额 = 1 + 3 = 4 。</pre>
//
//<p><strong>示例 2：</strong></p>
//
//<pre>
//<strong>输入：</strong>[2,7,9,3,1]
//<strong>输出：</strong>12
//<strong>解释：</strong>偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。
//     偷窃到的最高金额 = 2 + 9 + 1 = 12 。
//</pre>
//
//<p> </p>
//
//<p><strong>提示：</strong></p>
//
//<ul>
//	<li><code>1 <= nums.length <= 100</code></li>
//	<li><code>0 <= nums[i] <= 400</code></li>
//</ul>
//<div><div>Related Topics</div><div><li>数组</li><li>动态规划</li></div></div><br><div><li>👍 2203</li><li>👎 0</li></div>

package com.rising.leetcode.editor.cn;

/**
 * 打家劫舍
 * @author DY Rising
 * @date 2022-07-13 20:20:50
 */
public class P198_HouseRobber{
    public static void main(String[] args) {
        //测试代码
        Solution solution = new P198_HouseRobber().new Solution();
        System.out.println(solution.rob(new int[]{1,3,1}));

        /**
         * 设方法f(n) 为n个房子偷窃价值最大
         * 1、假设不偷n-1，则f(n) = f(n-2) + nums[n]
         * 2、假设偷n-1，则f(n) = f（n-1）
         * 最终f(n) = max(f（n-1）, f(n-2) + nums[n])
         *
         */
    }

    //力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int rob(int[] nums) {
        if (nums.length == 1) return nums[0];
        if (nums.length == 2) return Math.max(nums[0], nums[1]);
        int[] sum = new int[nums.length];
        sum[0] = nums[0];
        sum[1] = Math.max(nums[0], nums[1]);
        for (int i = 2; i < nums.length; i++) {
            sum[i] = Math.max(sum[i-1], sum[i-2] + nums[i]);
        }
        return sum[sum.length - 1];
        //return dsf(nums, nums.length);
    }

        /**
         * 递归
         * @param nums
         * @param n
         * @return
         */
    public int dsf(int[] nums, int n) {
        if (n == 1) {
            return nums[0];
        }
        if (n == 2) {
            return Math.max(nums[0], nums[1]);
        }
        return Math.max(dsf(nums, n - 1), dsf(nums, n - 2) + nums[n - 1]);
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}
